package com.acme.gclab;

import java.nio.ByteBuffer;
import java.util.*;

public class ByteBufferHashMap implements Map<Integer, Integer> {

    private static final int INT_SIZE = 4;
    private static final int ENTRY_OFFSET = 12;

    private static final double BUCKETS_FRACTION = 0.1;
    private int bucketPartSize;

    private int firstEmptyEntryIndex;

    private int size;

    private ByteBuffer byteBuffer;

    private boolean zeroPutted = false;
    private int zeroValue;


    public ByteBufferHashMap(ByteBuffer byteBuffer) {
        this.byteBuffer = byteBuffer;
        prepareBuffer();
    }

    private void prepareBuffer() {
        int total = byteBuffer.capacity();

        bucketPartSize = INT_SIZE * (((int) Math.round(total * BUCKETS_FRACTION)) / INT_SIZE);
        firstEmptyEntryIndex = bucketPartSize;

        size = 0;
    }

    private int findOrCreateBucket(int key) {
        int index = getBucketHeaderIndex(key);
        int position = byteBuffer.getInt(index);
        if (position == 0) {
            position = getFirstEmptyEntryIndex();
            byteBuffer.putInt(index, position);
        }
        return position;
    }

    private int putInt(int key, int value) {

        if (key == 0) {
            return putZero(value);
        }

        int position = findOrCreateBucket(key);

        Entry entry = new Entry(byteBuffer, position);
        Entry newEntry;

        if (entry.isEmpty()) {
            newEntry = entry;
        } else {
            while (entry.getNextEntry() != null) {
                entry = entry.getNextEntry();
            }
            newEntry = new Entry(byteBuffer, getFirstEmptyEntryIndex());
            entry.setNextIndex(getFirstEmptyEntryIndex());
        }

        newEntry.setKey(key);
        newEntry.setValue(value);
        newEntry.setNextIndex(0);

        size++;
        findNextFirstEmptyEntryIndex();

        return value;
    }

    private Integer getInt(int key) {
        if (key == 0) {
            if (zeroPutted) {
                return zeroValue;
            } else {
                return null;
            }
        }

        int position = byteBuffer.getInt(getBucketHeaderIndex(key));

        if (position == 0) {
            return null;
        } else {
            Entry entry = new Entry(byteBuffer, position);
            do {
                if (entry.getKey() == key) {
                    return entry.getValue();
                }
                entry = entry.getNextEntry();
            } while (entry != null);

            return null;
        }
    }

    private Integer removeInt(int key) {
        if (key == 0) {
            return removeZero();
        }

        int index = getBucketHeaderIndex(key);
        int firstEntryIndex = byteBuffer.getInt(index);

        if (firstEntryIndex == 0) {
            return null;
        }

        Entry entry = new Entry(byteBuffer, firstEntryIndex);

        if (entry.getKey() == key) {
            setFirstEmptyEntryIndex(entry.getIndex());
            byteBuffer.putInt(index, entry.getNextIndex());
            entry.setKey(0).setNextIndex(0);
            size--;
            return entry.getValue();
        }

        if (entry.getNextEntry() == null) {
            return null;
        }

        do {
            Entry nextEntry = entry.getNextEntry();
            if (nextEntry.getKey() == key) {
                setFirstEmptyEntryIndex(nextEntry.getIndex());
                entry.setNextIndex(nextEntry.getNextIndex());
                nextEntry.setKey(0).setNextIndex(0);
                size--;
                return nextEntry.getValue();
            }
            entry = nextEntry;
        } while (entry.getNextEntry() != null);

        return null;
    }


    private int putZero(int value) {
        if (zeroPutted) {
            return zeroValue;
        } else {
            zeroValue = value;
            zeroPutted = true;
            size++;
            return value;
        }
    }

    private Integer removeZero() {
        if (zeroPutted) {
            zeroPutted = false;
            size--;
            return zeroValue;
        } else {
            return null;
        }
    }

    private void setFirstEmptyEntryIndex(int index) {
        if (index < firstEmptyEntryIndex) {
            firstEmptyEntryIndex = index;
        }
    }

    private int getFirstEmptyEntryIndex() {
        if (firstEmptyEntryIndex + ENTRY_OFFSET >= byteBuffer.capacity()) {
            throw new NoMoreSpaceException();
        }
        return firstEmptyEntryIndex;
    }

    private void findNextFirstEmptyEntryIndex() {
        if (byteBuffer.getInt(firstEmptyEntryIndex) == 0) return;
        while ((firstEmptyEntryIndex + ENTRY_OFFSET < byteBuffer.capacity() - 3) && (byteBuffer.getInt(firstEmptyEntryIndex + ENTRY_OFFSET) != 0)) {
            firstEmptyEntryIndex += ENTRY_OFFSET;
        }
        firstEmptyEntryIndex += ENTRY_OFFSET;
    }

    private int getBucketHeaderIndex(int key) {
        return INT_SIZE * (key % (bucketPartSize / INT_SIZE));
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean containsKey(Object key) {
        return get(key) != null;
    }

    @Override
    public boolean containsValue(Object value) {
        return false;
    }

    @Override
    public Integer get(Object key) {
        if (key instanceof Integer) {
            return getInt((Integer) key);
        }
        throw new UnsupportedOperationException();
    }

    @Override
    public Integer put(Integer key, Integer value) {
        return putInt(key, value);
    }

    @Override
    public Integer remove(Object key) {
        if (!(key instanceof Integer)) throw new IllegalArgumentException("Integer requires as key");

        return removeInt((Integer) key);
    }

    @Override
    public void putAll(Map<? extends Integer, ? extends Integer> m) {
        for (Map.Entry<? extends Integer, ? extends Integer> entry : m.entrySet()) {
            put(entry.getKey(), entry.getValue());
        }
    }

    @Override
    public void clear() {
        for (int i = 0; i < byteBuffer.capacity(); i++) {
            byteBuffer.putInt(i, 0);
        }
        prepareBuffer();
    }

    @Override
    public Set<Integer> keySet() {
        Set<Integer> result = new HashSet<Integer>();
        for (int i = 0; i < bucketPartSize / INT_SIZE; i++) {
            int position = byteBuffer.getInt(i * INT_SIZE);
            if (position != 0) {
                Entry entry = new Entry(byteBuffer, position);
                do {
                    result.add(entry.getKey());
                    entry = entry.getNextEntry();
                } while (entry != null);
            }
        }
        return result;
    }

    @Override
    public Collection<Integer> values() {
        Set<Integer> result = new HashSet<Integer>();
        for (int i = 0; i < bucketPartSize / INT_SIZE; i++) {
            int position = byteBuffer.getInt(i * INT_SIZE);
            if (position != 0) {
                Entry entry = new Entry(byteBuffer, position);
                do {
                    result.add(entry.getValue());
                    entry = entry.getNextEntry();
                } while (entry != null);
            }
        }
        return result;
    }

    @Override
    public Set<Map.Entry<Integer, Integer>> entrySet() {
        Set<Map.Entry<Integer, Integer>> result = new HashSet<Map.Entry<Integer, Integer>>();
        for (int i = 0; i < bucketPartSize / INT_SIZE; i++) {
            int position = byteBuffer.getInt(i * INT_SIZE);
            if (position != 0) {
                Entry entry = new Entry(byteBuffer, position);
                do {
                    result.add(new AbstractMap.SimpleEntry<Integer, Integer>(entry.getKey(), entry.getValue()));
                    entry = entry.getNextEntry();
                } while (entry != null);
            }
        }
        return result;
    }

    public class Entry {
        private static final int KEY_OFFSET = 0;
        private static final int VALUE_OFFSET = 4;
        private static final int NEXT_OFFSET = 8;

        private ByteBuffer buffer;

        private int keyIndex;
        private int valueIndex;
        private int nextIndex;

        private Entry(ByteBuffer buffer, int index) {
            this.buffer = buffer;

            keyIndex = index + KEY_OFFSET;
            valueIndex = index + VALUE_OFFSET;
            nextIndex = index + NEXT_OFFSET;
        }

        private int getIndex() {
            return keyIndex;
        }

        private Entry setKey(int key) {
            buffer.putInt(keyIndex, key);
            return this;
        }

        private Entry setValue(int value) {
            buffer.putInt(valueIndex, value);
            return this;
        }

        private Entry setNextIndex(int next) {
            buffer.putInt(nextIndex, next);
            return this;
        }

        public int getKey() {
            return buffer.getInt(keyIndex);
        }

        public int getValue() {
            return buffer.getInt(valueIndex);
        }

        public Entry getNextEntry() {
            int nextIndex = buffer.getInt(this.nextIndex);
            if (nextIndex == 0) return null;
            return new Entry(buffer, nextIndex);
        }

        public int getNextIndex() {
            return buffer.getInt(this.nextIndex);
        }

        public boolean exist() {
            return byteBuffer.capacity() > nextIndex + INT_SIZE - 1;
        }

        public boolean isEmpty() {
            return getKey() == 0;
        }
    }

    public static class NoMoreSpaceException extends RuntimeException {

    }

}
